package com.hanxiaozhang.no10leetcode.link;

/**
 * 〈一句话功能简述〉<br>
 * 〈合并k个已排序的list〉
 * 实例:
 * 输入: [ 1->4->5, 1->3->4, 2->6 ]
 * 输出: 1->1->2->3->4->4->5->6
 *
 *
 * @author hanxinghua
 * @create 2024/1/31
 * @since 1.0.0
 */
public class No23MergeKSortedLists {

    public static void main(String[] args) {


        Node node1 = new Node(1);
        node1.next = new Node(4);
        node1.next.next = new Node(5);

        Node node2 = new Node(1);
        node2.next = new Node(3);
        node2.next.next = new Node(4);

        Node node3 = new Node(2);
        node3.next = new Node(6);

        Node[] nodes = {node1, node2, node3};

        Node node = method2(nodes);
        LinkUtil.printLink(node);

    }

    /**
     * 方法2
     * 基于两个已排序链表合并，使用 归并排序的思想，两两合并最后完全合并
     *
     * @param Nodes
     * @return
     */
    private static Node method2(Node... Nodes) {

        return split(Nodes, 0, Nodes.length - 1);
    }

    /**
     * 将多个链表，两两比较。
     *
     * @param nodes
     * @param start
     * @param end
     * @return
     */
    public static Node split(Node[] nodes, int start, int end) {

        // 开始位置等于结束位置时，返回该链表，不用比较
        if (start == end) {
            return nodes[start];
        }

        int mid = start + (end - start) / 2;
        Node left = split(nodes, start, mid);
        Node right = split(nodes, mid + 1, end);

        return mergeTwoSorted(left, right);
    }


    /**
     * 方法1
     *
     * @param nodes
     * @return
     */
    private static Node method1(Node... nodes) {

        if (nodes == null) {
            return null;
        }
        if (nodes.length == 1) {
            return nodes[0];
        }
        Node node = mergeTwoSorted(nodes[0], nodes[1]);
        for (int i = 2; i < nodes.length; i++) {
            node = mergeTwoSorted(node, nodes[i]);
        }
        return node;
    }


    private static Node mergeTwoSorted(Node<Integer> node1, Node<Integer> node2) {

        Node puppet = new Node(-1);
        Node cur = puppet;

        while (node1 != null && node2 != null) {
            if (node1.data < node2.data) {
                cur.next = node1;
                node1 = node1.next;
            } else {
                cur.next = node2;
                node2 = node2.next;
            }
            cur = cur.next;
        }
        if (node1 != null) {
            cur.next = node1;
        } else {
            cur.next = node2;
        }
        return puppet.next;
    }


}
